package syf.rank;

import java.util.Arrays;

public class QuickRank {
    public static void main(String[] args) {
        int[] arr={-9,78,0,80,-567,70};
//        int max=8000000;
//        int[] arr=new int[max];
//        //8万个随机的数组排序
//        for (int i=0;i<max;i++){
//            arr[i]=(int)(Math.random()*100);
//        }
//        System.out.println(Arrays.toString(arr));
        long now=System.currentTimeMillis();
        arr=quick(arr,0,arr.length-1);
        long end=System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println(end-now);//1627ms左右
    }
    /**
     * 快速排序
     * @param arr 需要排序的数组
     * @param left 最左下标
     * @param right 最右下标
     * @return 排序后数组
     */
    public static int[] quick(int[] arr,int left,int right) {
        //交换暂时值
        int tmp;
        //最中间的值
        int mid=arr[(right+left)/2];
        //首次标记左右两边的值
        int r=right;
        int l=left;
        //将比中间值小的放左边，大的放右边
        while (r>l){
            //找到左边比中间值大的,当左边的当前值比中间值小时继续往右走，等于中间值退出
            while (arr[l]<mid){
                l++;
            }
            //找到右边比中间值小的,当右边的当前值比中间值大时继续往左走，等于中间值退出
            while (arr[r]>mid){
                r--;
            }
            //说明此时已经不满足条件直接退出加快速度
            if (r<=l)
                break;
            //走完上面两个以后，即得到了各自大于和小于的 交换
            tmp=arr[r];
            arr[r]=arr[l];
            arr[l]=tmp;
            //如果上面找到的值和中间值相等会一直卡住，所以需要帮助他们前进或后退一格
            //arr[r]为l交换后的
            if (arr[r]==mid){
                l++;
            }
            //arr[l]为l交换后的
            if (arr[l]==mid){
                r--;
            }
        }
        //交换后左右两个下标索引已经再中间了，需帮助加减，否则栈溢出
        if (r==l){
            r--;
            l++;
        }
        //对左边的数进行递归排序
        if (r>left)
            quick(arr,left,r);
        //对右边的数进行递归排序
        if (right>l)
            quick(arr,l,right);
        return arr;
    }
}
/*
    int l=left;
        int r=right;
        //中轴值
        int mid=arr[(l+r)/2];
        int tmp;
        while (l<r){
            while (arr[l]<mid){
                l++;
            }
            while (arr[r]>mid){
                r--;
            }
            if (l>=r)
                break;
            //交换
            tmp=arr[r];
            arr[r]=arr[l];
            arr[l]=tmp;
            if (arr[l]==mid)
                r--;
            if (arr[r]==mid)
                l++;
        }
        if (r==l){
            l++;
            r--;
        }
        if (left<r)
            quick(arr,left,r);
        if (right>l)
            quick(arr,l,right);
        return arr;
* */